package algorithm;

import java.util.Arrays;

public class SumOfTwoNumbers {
    public static int[] twoSumV(int[] price,int target) {
         //暴力解
        //在leetcode上是超时的
         int[] result = new int[2];
         for(int i = 0;i < price.length;i++) {
             for(int j = i + 1;j < price.length;j++) {
                  if(price[i] + price[j] == target) {
                      result[0] = price[i];
                      result[1] = price[j];
                  }
             }
         }

          return result;
    }
    public static int[] twoSum(int[] price,int target) {
        //利用单调性和双指针算法，在O(n)的时间复杂度之内解决该问题
        int left = 0;
        int right = price.length - 1;

        int[] result = new int[2];
        while(left < right) {
            int sum = price[left] + price[right];
            if(sum == target) {
                result[0] = price[left];
                result[1] = price[right];
                return result;
            } else if(sum < target) {
                left++;
            } else {
                right--;
            }
        }

        return result;
    }
    public static void main(String[] args) {
        int[] price = new int[]{8, 21, 27, 34, 52, 66};
        int target = 61;
        System.out.println(Arrays.toString(twoSum(price,target)));
    }
}
